Vierfarbenproblem

Vierfarbenproblem,

 

ein mathematisches Problem der Graphentheorie (Graph), das um 1852 von englischen Kartographen entdeckt und 1878/79 von A. Cayley in der Fachwelt verbreitet wurde. In seiner ursprünglichen Formulierung stellt es die Frage, ob die Länder jeder Landkarte mit höchstens vier Farben so gefärbt werden können, dass je zwei Länder, die ein gemeinsames Grenzstück besitzen, verschiedene Farben tragen. Das Vierfarbenproblem hat für die Entwicklung der Graphentheorie eine bedeutende Rolle gespielt und wurde nach Vorarbeiten von Heinrich Heesch (* 1906, ✝ 1990) und weiteren Mathematikern 1976 von Kenneth Appel (* 1932) und Wolfgang Haken (* 1928) positiv beantwortet. Der angegebene Beweis beruht, auf der Grundlage komplizierter graphentheoretischer Methoden, wesentlich auf dem Existenznachweis einer endlichen Menge von weniger als zweitausend reduziblen Teilgraphen ebener Triangulierungen, deren Reduzibilität für jeden Teilgraphen rechnerunterstützt geprüft wird.